package Tests;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.TreeMap;
import java.util.Map.Entry;

import CSP.Constraint;


public class BacktrackingLogic {	
	/**
	 * Backtracking-Method
	 * @param assigns that were made from the variables & constraints, initial:_empty
	 * @param variables here: seats, numbered from 1 to numberOfSeats
	 * @param domainBT contains the names
	 * @returns the assigns made from the variables & constraints
	 */
	public TreeMap<Integer, String> Backtracking(TreeMap<Integer, String> assigns, List<Integer> variables, List<String> domainBT) {
		if(variables.size() == 0 || domainBT.size() == 0)
		{
			// Create the "result: {(Position, Name)}"-String
			int tmp = 0;
			String result = "";
			
			result += "result: {";			
			for(Entry<Integer, String> entry : assigns.entrySet())
			{
				result += "(" + entry.getKey() + ", " + entry.getValue() + ")";
				tmp++;
				
				if(entry.equals(assigns.lastEntry()))
					result += "}";
				else
					result +=", ";
				
				if(tmp == 2)
				{
					outputCode.add(result);
					tmp = 0;
					result = "";
				}
			}
			
			return assigns;
		}
		
		int current = variables.get(0);
		outputCode.add("Select " + current);
		
		int check = 42;
		TreeMap<Integer, String> result;		
		ArrayList<String> alternatives = new ArrayList<String>();
		
		// Check for first assigns (wishes)
		for(int i = 0; i < domainBT.size(); i++)
		{			
			// Constraints-check
			if(current == 1)	// Initial assignment (seat 1)
				check = checkConstraints(null, domainBT.get(i), null);
			else if(variables.size() == 1)	// last assignment (seat 10 e.g.)
				check = checkConstraints(assigns.get(assigns.lastKey()), domainBT.get(i), assigns.get(assigns.firstKey()));
			else	// normal assignment				
				check = checkConstraints(assigns.get(assigns.lastKey()), domainBT.get(i), null);
				
			
			switch(check) 
			{			
				case 0: 
					outputCode.add(current + " = " + domainBT.get(i) + " not consistent (" + constraints.get(domainBT.get(i)).getID() +")");
					break;
				
				case 1:
					// Adding assignment
					assigns.put(current, domainBT.get(i));
					
					// previous Strings are not consistent
					for(String s : alternatives)
						outputCode.add(current + " = " + s + " not consistent (" + constraints.get(domainBT.get(i)).getID() +")");
						
					outputCode.add(current + " = " + domainBT.get(i) + " consistent");
					variables.remove(0);
					domainBT.remove(domainBT.get(i));				
				
					// Recursion
					result = Backtracking(assigns, variables, domainBT);
				
					// Failure-Fall
					if(result != null)
						return result;
				
					// Backtrack-Fall
					variables.add(0, assigns.lastKey());
					domainBT.add(i, assigns.get(assigns.lastKey()));
					assigns.remove(current);
					outputCode.add("Backtrack");
					outputCode.add("Select " + current);
					break;
				
				case 2:
					alternatives.add(domainBT.get(i));
					break;
			}
		}
		// Check alternatives
		for(String s : alternatives)
		{
			// Adding assignment
			assigns.put(current, s);
			outputCode.add(current + " = " + s + " consistent");
			variables.remove(0);
			domainBT.remove(s);			
				
			// Recursion
			result = Backtracking(assigns, variables, domainBT);
				
			// Failure-Fall
			if(result != null)
					return result;
				
			// Backtrack-Fall
			variables.add(0, assigns.lastKey());
			domainBT.add(0, assigns.get(assigns.lastKey()));
			assigns.remove(current);
			outputCode.add("Backtrack");
		}
		return null;
	}
	
	/**
	 * Checks if a given person can sit next to 2 given persons left and right
	 * @param left person
	 * @param person to check
	 * @param right person
	 * @returns 0 if the person can't sit next to left or right
	 * @returns 1 if the person needs to sit next to either left or right
	 * @returns 2 if the person can sit next to left / right
	 */
	private int checkConstraints(String left, String person, String right) {
		if(checkLeft(left, person) == 0 || checkRight(person, right) == 0)
			return 0;
		if(checkLeft(left, person) == 1 && checkRight(person, right) == 1)
			return 1;
		
		return 2;
	}
	
	/**
	 * Checks if a given person can sit next to the left person
	 * @see checkConstraints
	 */
	private int checkLeft(String left, String person) {		
		if(left == null)
			return 1;

		Constraint cons;
		if(constraints.containsKey(person))
			cons = constraints.get(person);	
		else 
		{
			cons = new Constraint(person);
			constraints.put(person, cons);
		}
		
		return cons.consistent(left);
	}
	
	/**
	 * Checks if a given person can sit next to the right person
	 * @see checkConstraints
	 */
	private int checkRight(String person, String right) {
		if(right == null)
			return 1;
		
		Constraint cons;
		if(constraints.containsKey(person))
			cons = constraints.get(person);	
		else 
		{
			cons = new Constraint(person);
			constraints.put(person, cons);
		}
		
		return cons.consistent(right);
	}
	
	private class CodeLine {
		int code;
		int position;
		String person;
		
		public CodeLine(int code, int pos, String pers) {
			this.code = code;
			this.position = pos;
			this.person = pers;
		}
		
		public int getCode() {
			return this.code;
		}
		
		public int getPosition() {
			return this.position;
		}
		
		public String getPerson() {
			return this.person;
		}
	}
}
